package cn.leecode.q67;

/**
 * 简单题目67:二进制求和
 * 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
 * 示例 1：
 * 输入:a = "11", b = "1"
 * 输出："100"
 * 示例 2：
 * 输入：a = "1010", b = "1011"
 * 输出："10101"
 * 提示：
 * 1 <= a.length, b.length <= 104
 * a 和 b 仅由字符 '0' 或 '1' 组成
 * 字符串如果不是 "0" ，就不含前导零
 */
public class AddBinary {
    public String addBinary(String a, String b) {
        StringBuilder result = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        // 从末尾到开头循环两个字符串
        while (i >= 0 || j >= 0 || carry == 1) {
            if (i >= 0) carry += a.charAt(i--) - '0'; // 将char转换为int并将其添加到进位
            if (j >= 0) carry += b.charAt(j--) - '0'; // 将char转换为int并将其添加到进位
            // 将当前位添加到结果中。当前位为进位%2。
            result.append(carry % 2);
            // 更新下一次迭代的进位。如果有进位，则为1，否则为0。
            carry /= 2;
        }
        // 由于我们一直在以相反的顺序添加比特，因此我们需要在返回结果之前对其进行反转。
        return result.reverse().toString();
    }

    public static void main(String[] args) {
        AddBinary solution = new AddBinary();
        // Test cases
        System.out.println(solution.addBinary("11", "1")); // "100"
        System.out.println(solution.addBinary("1010", "1011")); // "10101"
    }
}
